By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 28, Issue 3, pp. 771-1153

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane

Joseph S. B. Mitchell, Avrim Blum, Prasad Chalasani, and Santosh Vempala

pp. 771-781

BibTeX  Abstract Full Text:  PDF

Solvability of Consensus: Composition Breaks Down for NonDeterministic Types

Prasad Jayanti

pp. 782-797

BibTeX  Abstract Full Text:  PDF

A Lower Bound for Integer Multiplication with Read-Once Branching Programs

Stephen Ponzio

pp. 798-815

BibTeX  Abstract Full Text:  PDF

Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors

Hugh Hind, Michael Molloy, and Bruce Reed

pp. 816-821

BibTeX  Abstract Full Text:  PDF

Computing components and projections of curves over finite fields

Joachim von zur Gathen and Igor Shparlinski

pp. 822-840

BibTeX  Abstract Full Text:  PDF

Bipartite Edge Coloring in $O(\Delta m)$ Time

Alexander Schrijver

pp. 841-846

BibTeX  Abstract Full Text:  PDF

Row-Major Sorting on Meshes

Jop F. Sibeyn

pp. 847-863

BibTeX  Abstract Full Text:  PDF

Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design

Giuseppe Liotta, Franco P. Preparata, and Roberto Tamassia

pp. 864-889

BibTeX  Abstract Full Text:  PDF

Failure Detection and Randomization: A Hybrid Approach to Solve Consensus

Marcos Kawazoe Aguilera and Sam Toueg

pp. 890-903

BibTeX  Abstract Full Text:  PDF

Average Profile of the Generalized Digital Search Tree and the Generalized Lempel--Ziv Algorithm

Guy Louchard, Wojciech Szpankowski, and Jing Tang

pp. 904-934

BibTeX  Abstract Full Text:  PDF

The Maximum Partition Matching Problem with Applications

Chi-Chang Chen and Jianer Chen

pp. 935-954

BibTeX  Abstract Full Text:  PDF

Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions

Ming-Yang Kao, Junfeng Qi, and Lei Tan

pp. 955-969

BibTeX  Abstract Full Text:  PDF

Three-Processor Tasks Are Undecidable

Eli Gafni and Elias Koutsoupias

pp. 970-983

BibTeX  Abstract Full Text:  PDF

Simple Algorithms for Routing on Butterfly Networks with Bounded Queues

Bruce M. Maggs and Ramesh K. Sitaraman

pp. 984-1003

BibTeX  Abstract Full Text:  PDF

Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs

Wen-Lian Hsu and Tze-Heng Ma

pp. 1004-1020

BibTeX  Abstract Full Text:  PDF

Fast Connected Components Algorithms for the EREW PRAM

David R. Karger, Noam Nisan, and Michal Parnas

pp. 1021-1034

BibTeX  Abstract Full Text:  PDF

Products and Help Bits in Decision Trees

Noam Nisan, Steven Rudich, and Michael Saks

pp. 1035-1050

BibTeX  Abstract Full Text:  PDF

A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata

Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa

pp. 1051-1072

BibTeX  Abstract Full Text:  PDF

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)

Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, and Mikkel Thorup

pp. 1073-1085

BibTeX  Abstract Full Text:  PDF

Competitive On-Line Algorithms for Distributed Data Management

Carsten Lund, Nick Reingold, Jeffery Westbrook, and Dicky Yan

pp. 1086-1111

BibTeX  Abstract Full Text:  PDF

Efficient Database Updates with Independent Schemes

Riccardo Torlone and Paolo Atzeni

pp. 1112-1135

BibTeX  Abstract Full Text:  PDF

Learning DNF over the Uniform Distribution Using a Quantum Example Oracle

Nader H. Bshouty and Jeffrey C. Jackson

pp. 1136-1153

BibTeX  Abstract Full Text:  PDF